package Algorithm.DoublePointer;

import java.util.Deque;
import java.util.LinkedList;

public class leetcode42 {
    class Solution {
        public int trap(int[] height) {
            Deque<Integer> stack = new LinkedList<Integer>();
            int sum = 0;

            for(int i=0;i<height.length;i++){
                while(stack.peekFirst()!=null&&height[stack.peekFirst()]<height[i]){
                    int index = stack.pollFirst();
                    if(stack.peekFirst()!=null){
                        sum = sum + (Math.min(height[stack.peekFirst()],height[i]) - height[index]) * (i-stack.peekFirst()-1);
                    }
                }
                stack.offerFirst(i);

            }
            return sum;
        }
    }
}
